#ifndef _BUOLA_GRAPH_CSUBGRAPH_H_
#define _BUOLA_GRAPH_CSUBGRAPH_H_

#include <buola/buola.h>
#include <buola/iterator/wrap.h>
#include <buola/iterator/filter.h>
#include <list>
#include <vector>
#include <boost/graph/adjacency_list.hpp>

namespace buola { namespace graph {

template<typename tGraph>
class CSubGraph
{
    struct AOutEdgeFilter
    {
        AOutEdgeFilter()=default;
        
        AOutEdgeFilter(const CSubGraph *pSG)
            :   mSG(pSG)
        {}
        
        bool operator()(const typename tGraph::edge_descriptor &pE)
        {
            return mSG->mReverseVertices[target(pE,mSG->mGraph)]>=0;
        }
        
        const CSubGraph *mSG;
    };
    
public:
    typedef typename tGraph::vertex_descriptor vertex_descriptor;
    typedef std::vector<vertex_descriptor> TVertexContainer;
    typedef typename TVertexContainer::const_iterator vertex_iterator;
    typedef typename tGraph::edge_descriptor edge_descriptor;
    typedef typename tGraph::directed_category directed_category;
    typedef typename tGraph::edge_parallel_category edge_parallel_category;
    typedef typename tGraph::traversal_category traversal_category;
    typedef IFilter<typename tGraph::out_edge_iterator,AOutEdgeFilter> out_edge_iterator;
    typedef size_t degree_size_type;

private:
    const tGraph &mGraph;
    std::vector<typename tGraph::vertex_descriptor> mVertices;
    std::vector<ssize_t> mReverseVertices;

public:
    template<typename tRange>
    CSubGraph(const tGraph &pGraph,tRange &&pRange)
        :   mGraph(pGraph)
        ,   mVertices(range_begin(pRange),range_end(pRange))
    {
        mReverseVertices.resize(num_vertices(mGraph),-1);
        for(int i=0;i<mVertices.size();i++)
        {
            mReverseVertices[mVertices[i]]=i;
        }
    }
    
    auto EdgeMap() const -> decltype(this->mGraph.EdgeMap())
    {
        return mGraph.EdgeMap();
    }

    auto VertexMap() const -> decltype(this->mGraph.VertexMap())
    {
        return mGraph.VertexMap();
    }
    
    CRange<vertex_iterator> Vertices() const
    {
        return range(mVertices);
    }

    size_t NumVertices() const
    {
        return mVertices.size();
    }
    
    CRange<out_edge_iterator> OutEdges(const vertex_descriptor &pV) const
    {
        return filter_range(boost::out_edges(pV,mGraph),AOutEdgeFilter(this));
    }
    
    vertex_descriptor Target(const edge_descriptor &pE) const
    {
        return boost::target(pE,mGraph);
    }

    vertex_descriptor Source(const edge_descriptor &pE) const
    {
        return boost::source(pE,mGraph);
    }
    
    vertex_descriptor MaxVertexDescriptor() const
    {
        return mGraph.MaxVertexDescriptor();
    }
    
    static vertex_descriptor null_vertex()
    {
        return tGraph::null_vertex();
    }
};

template<typename tGraph>
CRange<typename CSubGraph<tGraph>::vertex_iterator> vertices(const CSubGraph<tGraph> &pSG)
{
    return pSG.Vertices();
}

template<typename tGraph>
size_t num_vertices(const CSubGraph<tGraph> &pSG)
{
    return pSG.NumVertices();
}

template<typename tGraph>
auto out_edges(const typename tGraph::vertex_descriptor &pV,const CSubGraph<tGraph> &pSG) -> decltype(pSG.OutEdges(pV))
{
    return pSG.OutEdges(pV);
}

template<typename tGraph>
size_t out_degree(const typename tGraph::vertex_descriptor &pV,const CSubGraph<tGraph> &pSG)
{
    return range_size(out_edges(pV,pSG));
}

template<typename tGraph>
typename tGraph::vertex_descriptor target(const typename tGraph::edge_descriptor &pE,const CSubGraph<tGraph> &pSG)
{
    return pSG.Target(pE);
}

template<typename tGraph>
typename tGraph::vertex_descriptor source(const typename tGraph::edge_descriptor &pE,const CSubGraph<tGraph> &pSG)
{
    return pSG.Source(pE);
}

template<typename tGraph,typename tRange>
CSubGraph<tGraph> make_subgraph(const tGraph &pGraph,tRange &&pRange)
{
    return {pGraph,std::forward<tRange>(pRange)};
}

/*namespace graph*/ } /*namespace buola*/ }

#endif
